﻿//
// $HeadURL: http://codeka-memcache.googlecode.com/svn/trunk/Codeka.Memcache/FastHasher.cs $
// $Revision: 4 $
// $Author: dean.codeka $     $Date: 2010-02-13 23:21:02 +0000 (Sat, 13 Feb 2010) $
//
// Copyright © 2009-2010 Dean Harding, all rights reserved.
//


using System.Text;
namespace Codeka.Memcache
{
    /// <summary>
    /// This class takes a string and returns a 32-bit hash of the string. I have
    /// chosen to use this rather than the built-in <b>string.GetHashCode</b> for
    /// the main reason that I know it's properties - I don't know what the built-
    /// in <b>string.GetHashCode</b> does...
    /// </summary>
    /// <remarks>
    /// <para>Ported to C# from http://www.azillionmonkeys.com/qed/hash.html </para>
    /// <para>The main thing slowing this class down is the bounds checking that .NET
    /// does. We could probably speed it up by disabling bounds checking (in an unsafe
    /// block) but that's mean we're no longer PartialTrust-compatible (does that matter
    /// if we're making socket connections?)</para>
    /// </remarks>
    public class FastHasher
    {
        /// <summary>
        /// Hashes the given <c>string</c> and return a 32-bit hashcode.
        /// </summary>
        public uint Hash(string value)
        {
            // note: our hash function works with byte arrays, but to make this
            // as fast as possible, we don't use UTF-8, just the raw UTF-16 bytes
            byte[] bytes = Encoding.Unicode.GetBytes(value);
            return Hash(bytes, 0, bytes.Length);
        }

        /// <summary>
        /// Hashes the given <c>byte</c> array and returns a 32-bit hashcode.
        /// </summary>
        public uint Hash(byte[] value, int offset, int count)
        {
            if (count <= 0 || value == null)
                return 0;

            uint hash = (uint) count;
            int remaining = count & 3;
            count >>= 2;

            int i = offset;
            for (; i < offset + count; i += 4)
            {
                hash += GetTwoBytes(value, i);
                uint temp = (GetTwoBytes(value, i + 2) << 11) ^ hash;
                hash = (hash << 16) ^ temp;
                hash += hash >> 11;
            }

            switch (remaining)
            {
                case 3:
                    hash += GetTwoBytes(value, i);
                    hash ^= hash << 16;
                    hash ^= ((uint) value[i+2]) << 18;
                    hash += hash >> 11;
                    break;
                case 2:
                    hash += GetTwoBytes(value, i);
                    hash ^= hash << 11;
                    hash += hash >> 17;
                    break;
                case 1:
                    hash += value[i];
                    hash ^= hash << 10;
                    hash += hash >> 1;
                    break;
            }

            hash ^= hash << 3;
            hash += hash >> 5;
            hash ^= hash << 4;
            hash += hash >> 17;
            hash ^= hash << 25;
            hash += hash >> 6;

            return hash;
        }

        private static uint GetTwoBytes(byte[] bytes, int offset)
        {
            uint a = bytes[offset];
            uint b = bytes[offset + 1];
            return ((a << 8) | b);
        }
    }
}
